package datastructure.book.tujiesuanfa.tree._2_more;

import datastructure.book.tujiesuanfa.tree.bean.TreeNode;

import java.util.LinkedList;

/**
 * 序列化与反序列化二叉树
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);
        while (!treeNodes.isEmpty()){
            LinkedList<TreeNode> tempTreeNodes = new LinkedList<>();
            for (TreeNode treeNode : treeNodes) {
                if (treeNode == null){
                    sb.append("n").append("|");
                }else {
                    sb.append(treeNode.val).append("|");
                    tempTreeNodes.add(treeNode.left);
                    tempTreeNodes.add(treeNode.right);
                }
            }
            treeNodes = tempTreeNodes;
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()){
            return null;
        }
        String[] split = data.split("\\|");
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        int index = 0;
        TreeNode result = new TreeNode(Integer.parseInt(split[0]));
        treeNodes.add(result);
        while (!treeNodes.isEmpty()){
            TreeNode treeNode = treeNodes.removeFirst();
            index++;
            if (index < split.length){
                if (!"n".equals(split[index])){
                    TreeNode left = new TreeNode(Integer.parseInt(split[index]));
                    treeNode.left = left;
                    treeNodes.add(left);
                }
            }
            index++;
            if (index < split.length){
                if (!"n".equals(split[index])){
                    TreeNode right = new TreeNode(Integer.parseInt(split[index]));
                    treeNode.right = right;
                    treeNodes.add(right);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Codec codec = new Codec();
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3,node4,node5);
        TreeNode node1 = new TreeNode(1,node2,node3);
        String serialize = codec.serialize(node1);
        System.out.println(serialize);
        codec.deserialize(serialize);
    }
}
